Міністерство освіти та науки України
Національний університет «Львівська політехніка»
Кафедра автоматизованих систем управління
Лабораторна робота №8
з дисципліни
«Комп’ютерна графіка»
на тему:
“ Растрова розгортка багатокутників ”.
Мета: Ознайомлення з основами комп‘ютерної графіки.
Теоретичні основи.
Можна розробити більш ефективний метод, ніж тест на приналежність внутрішньої частини, якщо скористатися тим фактом, що сусідні піксели, ймовірно, мають однакові характеристики (крім пікселів граничних ребер). Ця властивість називається просторовою когерентністю. Для растрових графічних пристроїв сусідні піксели на скануючому рядку, ймовірно, мають однакові характеристики. Це когерентність растрових рядків.
Характеристики пікселів на даному рядку змінюються тільки там, де ребро багатокутника перетинає рядок. Ці перетини поділяють скануючий рядок на області.
Рис.3.1. Растрова розгортка суцільної області.
Для простого багатокутника на рис.3.1 рядок 2 перетинає багатокутник при х=1 і х=8. Одержуємо три області:
x<1
поза багатокутником
1(x(8
всередині багатокутника
x>8
поза багатокутником
Рядок 4 поділяється на п'ять областей:
x<1
поза багатокутником
1(x(4
всередині багатокутника
4<x<6
поза багатокутником
6(x(8
всередині багатокутника
x>8
поза багатокутником
Зовсім необов’язково, щоб точки перетинану для рядка 4 відразу визначалися у фіксованому порядку (ліворуч праворуч). Наприклад, якщо багатокутник задається списком вершин P1P2P3P4P5, а список ребер - послідовними парами вершин Р1Р2, Р2Р3, Р3Р4, P4P5, P5P1 то для рядка 4 будуть знайдені наступні точки перетину з ребрами багатокутника: 8, 6, 4, 1. Ці точки треба відсортувати в зростаючому порядку по х, тобто одержати 1, 4, 6, 8.
При визначенні інтенсивності, кольору і відтінку пікселів на скануючому рядку розглядаються пари відсортованих точок перетинань. Для кожного інтервалу, що задається парою перетинань, використовується інтенсивність чи колір заповнюваного багатокутника. Для інтервалів між парами перетинань і крайніх (від початку рядка до першої точки перетину і від останньої точки перетину до кінця рядка) використовується фонова інтенсивність чи колір. На рис.3.1 для рядка 4 у фоновий колір встановлені піксели: від 0 до 1, від 4 до 6, від 8 до 10, тоді як піксели від 1 до 4 і від 5 до 8 зафарбовані в колір багатокутника.
Точне визначення тих пікселів, що повинні активуватися вимагає деякої обережності. Розглянемо простий прямокутник, зображений на рис.3.2. Прямокутник має координати (1,1) (5,1), (5,4), (1,4). Скануючі рядки з 1 по 4 мають перетини з ребрами багатокутника при х=1 і 5. Згадаємо, що піксел адресується координатами свого лівого нижнього кута, виходить, для кожного з цих скануючих рядків будуть активовані піксели з x-координатами 1, 2, 3, 4 і 5. На рис.3.2(а) показаний результат. Помітимо, що площа, що покривається активованими пікселами, дорівнює 20, у той час як дійсна площа прямокутника дорівнює 12.
а
б
Рис. 3.2 Система координат рядків сканування.
Модифікація системи координат скануючого рядка і тесту активації усуває цю проблему, як це показано на рис.3.2(б). Вважається, що сканируючі рядки проходять через центри рядків пікселів, тобто через середини інтервалів, як це показано на рис.3.2(б). Тест активації модифікується в такий спосіб: перевіряється, чи лежить всередині інтервалу центр піксела, розташованого праворуч від перетину. Однак піксели все ще адресуються координатами лівого нижнього кута. Як показано на рис.3.2(б), результат даного методу коректний.
Горизонтальні ребра не можуть перетинати скануючий рядок і, таким чином, ігноруються. Це зовсім не означає, що їх немає на малюнку. Ці ребра формуються верхнім і нижнім рядками пікселів, як показано на рис.3.2. Рис.3.2 ілюструє коректність верхнього і нижнього ребер багатокутника, отриманих у результаті модифікації системи координат скануючих рядків.
Додаткові труднощі виникають при перетині скануючого рядка і багатокутника точно по вершині, як це показа...